// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/heap/slot-set.h"

namespace v8 {
namespace internal {

    TypedSlots::~TypedSlots()
    {
        Chunk* chunk = head_;
        while (chunk != nullptr) {
            Chunk* next = chunk->next;
            delete[] chunk->buffer;
            delete chunk;
            chunk = next;
        }
        head_ = nullptr;
        tail_ = nullptr;
    }

    void TypedSlots::Insert(SlotType type, uint32_t offset)
    {
        TypedSlot slot = { TypeField::encode(type) | OffsetField::encode(offset) };
        Chunk* chunk = EnsureChunk();
        DCHECK_LT(chunk->count, chunk->capacity);
        chunk->buffer[chunk->count] = slot;
        ++chunk->count;
    }

    void TypedSlots::Merge(TypedSlots* other)
    {
        if (other->head_ == nullptr) {
            return;
        }
        if (head_ == nullptr) {
            head_ = other->head_;
            tail_ = other->tail_;
        } else {
            tail_->next = other->head_;
            tail_ = other->tail_;
        }
        other->head_ = nullptr;
        other->tail_ = nullptr;
    }

    TypedSlots::Chunk* TypedSlots::EnsureChunk()
    {
        if (!head_) {
            head_ = tail_ = NewChunk(nullptr, kInitialBufferSize);
        }
        if (head_->count == head_->capacity) {
            head_ = NewChunk(head_, NextCapacity(head_->capacity));
        }
        return head_;
    }

    TypedSlots::Chunk* TypedSlots::NewChunk(Chunk* next, int capacity)
    {
        Chunk* chunk = new Chunk;
        chunk->next = next;
        chunk->buffer = new TypedSlot[capacity];
        chunk->capacity = capacity;
        chunk->count = 0;
        return chunk;
    }

    TypedSlotSet::~TypedSlotSet() { FreeToBeFreedChunks(); }

    void TypedSlotSet::FreeToBeFreedChunks()
    {
        base::MutexGuard guard(&to_be_freed_chunks_mutex_);
        std::stack<std::unique_ptr<Chunk>> empty;
        to_be_freed_chunks_.swap(empty);
    }

    void TypedSlotSet::ClearInvalidSlots(
        const std::map<uint32_t, uint32_t>& invalid_ranges)
    {
        Chunk* chunk = LoadHead();
        while (chunk != nullptr) {
            TypedSlot* buffer = chunk->buffer;
            int count = chunk->count;
            for (int i = 0; i < count; i++) {
                TypedSlot slot = LoadTypedSlot(buffer + i);
                SlotType type = TypeField::decode(slot.type_and_offset);
                if (type == CLEARED_SLOT)
                    continue;
                uint32_t offset = OffsetField::decode(slot.type_and_offset);
                std::map<uint32_t, uint32_t>::const_iterator upper_bound = invalid_ranges.upper_bound(offset);
                if (upper_bound == invalid_ranges.begin())
                    continue;
                // upper_bounds points to the invalid range after the given slot. Hence,
                // we have to go to the previous element.
                upper_bound--;
                DCHECK_LE(upper_bound->first, offset);
                if (upper_bound->second > offset) {
                    ClearTypedSlot(buffer + i);
                }
            }
            chunk = LoadNext(chunk);
        }
    }

} // namespace internal
} // namespace v8
